package hot100;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        int i = 0;
        int j = nums.length - 1;
        while (true) {
            int index = quicksort(nums, i, j);
            if (index == nums.length - k) return nums[index];
            else if (index < nums.length - k) i = index + 1;
            else j = index - 1;
        }
    }


    public int quicksort(int[] arr, int l, int r) {
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;  //！！！两个while不能交换顺序，j--必须在前，i++在后
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, l, i);
        return i;
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
